#include <bits/stdc++.h>
using namespace std;
//depth first search to get particular score
struct node
{
    int clr;
    int score;
};
int ans = -1e9;
int T;
int n;
node a[100005];

void dfs(int x,int sum)
{
    if(x == n+1)
    {
        ans = max(ans,sum);
        return ;
    }
    for(int i = 0; i <= 1; i++)
    {
        int nx = x + 1;
        a[nx].clr = i;
        bool flag = false;
        for(int j = nx-1; j >= 1; j--)
        {
            if(a[j].clr == i && a[nx].score == a[j].score)
            {
                flag = true;
                dfs(nx,sum+a[j].score);
                break;
            }
            else if(a[j].clr == i && a[nx].score != a[j].score)
            {
                flag = true;
                dfs(nx,sum);
                break;
            }

        }
        if(!flag)
        {
            flag = true;
            dfs(nx,sum);
            flag = false;
        }
        a[nx].clr = !i;
    }
}

int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin >> T;
    while(T--)
    {
        cin >> n;
        if(n <= 35)
        {
            for(int i = 1; i <= n; i++)
            {
                cin >> a[i].score;
            }
            ans = 0;
            dfs(1,0);
            cout << ans << endl;
        }
        else
        {
            int dp[1005][1005][2] = {};
            int lr = 0;
            int lb = 0;
            for(int i = 1; i <= n; i++)
            {
                for(int j = i-1; j >= 1; j--)
                {
                    for(int k = 0; k <= 1; k++)
                    {
                        if(a[i].score == a[j].score && a[j].clr == k)
                        {
                            dp[i][j][k] = max(dp[i][j][k]+a[j].score,dp[i][j][1-k]);
                        }
                    }
                }
            }
            int maxn = -1e9;
            for(int i = 1; i <= n-1; i++)
            {
                maxn = max({maxn,dp[n][i][1],dp[n][i][0]});
            }
            cout << maxn << endl;
        }
    }
    return 0;
}
